package me.mingshan.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/smallest-k-lcci/description/
 *
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 *
 * 示例：
 *
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 *
 * @author hanjuntao
 * @date 2025/7/3 0003
 */
public class L_面试题17_14_smallest_k_lcci {

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,7,2,4,6,8};
        int[] result = smallestK(arr, 4);
        System.out.println(Arrays.toString(result));

        int[] arr2 = new int[]{62577,-220,-8737,-22,-6,59956,5363,-16699,0,-10603,64,-24528,-4818,96,5747,2638,-223,37663,-390,35778,-4977,-3834,-56074,7,-76,601,-1712,-48874,31,3,-9417,-33152,775,9396,60947,-1919,683,-37092,-524,-8,1458,80,-8,1,7,-355,9,397,-30,-21019,-565,8762,-4,531,-211,-23702,3,3399,-67,64542,39546,52500,-6263,4,-16,-1,861,5134,8,63701,40202,43349,-4283,-3,-22721,-6,42754,-726,118,51,539,790,-9972,41752,0,31,-23957,-714,-446,4,-61087,84,-140,6,53,-48496,9,-15357,402,5541,4,53936,6,3,37591,7,30,-7197,-26607,202,140,-4,-7410,2031,-715,4,-60981,365,-23620,-41,4,-2482,-59,5,-911,52,50068,38,61,664,0,-868,8681,-8,8,29,412};
        System.out.println(Arrays.toString(smallestK(arr2, 131)));
    }

    /**
     * 创建大根堆
     *
     * 思路：
     * 1. 创建一个大根堆，堆的大小为k
     * 2. 遍历数组，将数组中的元素加入堆中，堆的大小为k
     * 3. 堆的大小为k，如果数组中的元素大于堆顶元素，则将堆顶元素弹出，将数组中的元素加入堆中
     * 4. 遍历结束后，堆中的元素即为最小的k个元素
     *
     *
     * 时间复杂度：O(nlogk)
     *
     * @param arr
     * @param k
     * @return
     */
    private static int[] smallestK(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k <= 0 || k > arr.length) {
            return new int[0];
        }
        // 创建大根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, Comparator.reverseOrder());

        for (int i = 0; i < arr.length; i++) {
            pq.offer(arr[i]);

            if (pq.size() > k) {
                pq.poll();
            }
        }

        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = pq.poll();
        }
        return res;
    }

}
